/*求众数2
题目：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。*/
/*思路：
   摩尔投票法：
       要找出现次数大于n/3的数，这种数在长度为n的数组中最多两个，因为如果超过两个，如为3个，则这3个数
       之和肯定超过n，不符合题目所给条件。所以可以先假设 两个候选人为cand1,和cand2，遍历数组，每次能
       得到1票，判断这1票投给的候选人，如果和cand1相同，则cand1的票数count1+1，和和cand1相同，则cand2
       的票数count2+1，投完就countine返回判断部分，如果都不同则两个候选人票数都-1，如果有一个候选人票
       数不足以-1，就要更换这个候选人为 此时这票投给的人。最后得的cand1，cand2的票数如果都>0说明这两个
       候选人的票数都有可能超过n/3，在遍历一遍数组，如果票数超过n/3则输出该候选人。*/
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int arr[]={3,2,3},ans[10]={0};
    int i,sz;
    sz= sizeof(arr)/sizeof(arr[0]);
    int cand1=arr[0],count1=0;
    int cand2=arr[0],count2=0;
    for(i=0;i<sz;i++)
    {
        //投票阶段
        if( cand1 == arr[i])
        {
            count1++;
            continue;
        }
        if(cand2 == arr[i])
        {
            count2++;
            continue;
        }
        //判断是否需要更换候选人，如果某个候选人此时票数为0，需要更换成该票数推选的候选人
        if( count1==0)
        {
            cand1 = arr[i];
            count1++;
            continue;
        }
        if( count2 == 0)
        {
            cand1 = arr[i];
            count2++;
            continue;
        }
        //走到这里说明该票与两个候选人都不同，两个候选人票数都抵消1票。
        count1--;
        count2--;
    }
    count1=0;
    count2=0;
    //再次遍历，确定两候选人的票数是否超过n/3.
    for(i=0;i<sz;i++)
    {
        if(arr[i]==cand1 )
          count1++;
        else if(arr[i]==cand2 )
          count2++;
    }

    int t=0;
    if( count1>sz/3)
       ans[t++]=cand1;
     if(count2>sz/3)
       ans[t++]=cand2;
    for(i=0;i<t;i++)
    {
       printf("%d ",ans[i]);
    }
    return 0;
}
